package fcbase

//该文件是单链表以及其一些操作的实现

import (
	"fmt"
)

type LNode struct {
	Data interface{}
	next *LNode
}

func NewLNode() *LNode {
	return &LNode{}
}

func CreateList(head *LNode, num []int) {
	cur := head
	for i := 0; i < len(num); i++ {
		cur.next = NewLNode()
		cur.next.Data = num[i]
		cur = cur.next
	}
}

func PrintList(head *LNode) {
	for cur := head.next; cur != nil; cur = cur.next {
		fmt.Print(cur.Data, " ")
	}
	fmt.Println()
}

//直接反向
func Reverse(head *LNode) {
	var pre *LNode
	cur := head.next
	for cur != nil {
		next := cur.next
		cur.next = pre
		pre = cur
		cur = next
	}
	head.next = pre
}

//插入, 从第二个节点开始, 一次取出插到头结点后面
func ReverseInsert(head *LNode) {
	cur := head.next.next
	head.next.next = nil

	for cur != nil {
		next := cur.next
		cur.next = head.next
		head.next = cur
		cur = next
	}
}

//从无序链表中删除重复项(使用hash, O(n))
func DelRepeat(head *LNode) {
	hash := make(map[int]bool)
	var pre *LNode
	for cur := head.next; cur != nil; {
		if _, ok := hash[cur.Data.(int)]; !ok {
			hash[cur.Data.(int)] = true
			pre = cur
			cur = cur.next
		} else {
			pre.next = cur.next
			cur = cur.next
		}
	}
}
